package DP_share;

public class Solution {
	public int maxProfit_121(int[] prices) {
		// dp[i][0] 代表手上没有股票 即为利润
		// dp[i][1] 代表手上持有股票
		int[][] dp = new int[prices.length][2];
		for (int i = 0; i < prices.length; i++) {
			// 定义基本情况
			if (i - 1 == -1) {
				dp[i][0] = 0;// 没买股票 或者卖出
				dp[i][1] = -prices[i];// 买了当天的股票
				continue;
			}
			// 假设：昨天就没买股票 选择：今天继续不买 和 昨天买了股票今天卖掉 那个值大
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
			// 假设：昨天持有股票 选择：今天继续持有 或者我昨天没有持有今天选择买
			dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);

		}
		return dp[prices.length][0];
	}

	/**
	 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
	 * 
	 * 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），
	 * 
	 * 设计一个算法来计算你所能获取的最大利润。
	 * 
	 * 注意：你不能在买入股票前卖出股票。
	 * 
	 * 只能交易一次
	 * 
	 * @param prices
	 * @return
	 */
	public int maxProfit_121_o1(int[] prices) {
		int n = prices.length;
		int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
		// 仅允许做一次交易则每天都试一下
		for (int i = 0; i < n; i++) {
			// 利润
			// 昨天没有持有 今天继续没有持有 昨天持有 几天卖出 这两个没有持有的状态哪个高
			// 要最高的利润
			dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
			// 昨天本来就持有 几天继续持有 昨天没持有 今天买入
			// 用利润买入 然后利润可能为负数
			dp_i_1 = Math.max(dp_i_1, -prices[i]);
		}
		return dp_i_0;
	}

	/**
	 * 
	 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
	 * 
	 * 设计一个算法来计算你所能获取的最大利润。
	 * 
	 * 你可以尽可能地完成更多的交易（多次买卖一支股票）
	 * 
	 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
	 * 
	 * 可交易多次
	 * 
	 * @param prices
	 * @return
	 */
	public int maxProfit_122(int[] prices) {
		int n = prices.length;
		int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
		// 可以做多笔交易
		for (int i = 0; i < prices.length; i++) {
			int temp = dp_i_0;// 将昨天未持有的情况保存下来

			dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
			// 今天持有股票 昨天就持有股票今天继续持有 昨天没有持有股票今天买入 这两种情况那种较好
			// 区别在于我用的是昨天的钱再去买就形成了多次交易的逻辑否则永远都是
			dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
		}

		return dp_i_0;
	}

	/**
	 * 加冷冻期 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
	 * 
	 * 设计一个算法计算出最大利润。在满足以下约束条件下，
	 * 
	 * 你可以尽可能地完成更多的交易（多次买卖一支股票）:
	 * 
	 * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
	 * 
	 * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
	 * 
	 * @param prices
	 * @return
	 */
	public int maxProfit_309(int[] prices) {
		int n = prices.length;
		int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;// 昨天未持有和 昨天持有
		int dp_pre_0 = 0;// 前天的值
		for (int i = 0; i < prices.length; i++) {
			int temp = dp_i_0;
			//
			dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
			// 买入的限制是前天
			dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
			dp_pre_0 = temp;
		}
		return dp_i_0;
	}

	/**
	 * 加手续费 给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；
	 * 
	 * 非负整数 fee 代表了交易股票的手续费用。
	 * 
	 * 你可以无限次地完成交易，但是你每次交易都需要付手续费。
	 * 
	 * 如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
	 * 
	 * 返回获得利润的最大值。 在买入时做限制
	 * 
	 * @param prices
	 * @param fee
	 * @return
	 */
	public int maxProfit(int[] prices, int fee) {
		int n = prices.length;
		int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
		// 可以做多笔交易
		for (int i = 0; i < prices.length; i++) {
			int temp = dp_i_0;

			dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
			// 今天持有股票 昨天就持有股票 昨天没有持有股票今天买入
			dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
		}

		return dp_i_0;
	}

	/**
	 * 限定 两笔 交易 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
	 * 
	 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
	 * 
	 * 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
	 * 
	 * @param prices
	 * @return
	 */
	public int maxProfit_123(int[] prices) {
		int dp_i_10 = 0, dp_i_11 = Integer.MIN_VALUE;
		int dp_i_20 = 0, dp_i_21 = Integer.MIN_VALUE;
		// 可以做多笔交易
		for (int i = 0; i < prices.length; i++) {

			dp_i_20 = Math.max(dp_i_20, dp_i_21 + prices[i]);
			dp_i_21 = Math.max(dp_i_21, dp_i_10 - prices[i]);
			dp_i_10 = Math.max(dp_i_10, dp_i_11 + prices[i]);
			dp_i_11 = Math.max(dp_i_11, -prices[i]);

		}

		return dp_i_20;
	}

	/**
	 * 限定 k 笔交易 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
	 * 
	 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
	 * 
	 * 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
	 * 
	 * @param k
	 * @param prices
	 * @return
	 */
	public int maxProfit_188(int k, int[] prices) {

		return 0;
	}

}
